#define _CRT_SECURE_NO_WARNINGS
#include"head.h"
//typedef struct Heap
//{
//	HPDataType* a;
//	int size;
//	int capacity;
//}Heap;

void HeapPrint(Heap* hp)
{
	for (int i = 0; i < hp->size; ++i)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}

void HeapInit(Heap* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}



// 堆的销毁
void HeapDestory(Heap* hp)
{
	hp->size = 0;
	free(hp->a);

}

//调整为堆
void Adjustup(HPDataType* a, int child)
{

	int parent = (child - 1) / 2;

	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap( &a[child], & a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//交换函数
void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		Heap* tmp = (Heap*)realloc(hp->a, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newcapacity;

	}


	hp->a[hp->size] = x;
	hp->size++;
	Adjustup(hp->a, hp->size - 1);

}


//向下调整
void Adjustdown(HPDataType* a, int parent,int size)
{

	int minchild = 2 * parent - 1;

	while (minchild < size)
	{
		if (minchild + 1 < size && a[minchild] > a[minchild + 1])
		{
			minchild += 1;
		}

		if ( a[parent] < a[minchild])
		{
			Swap(&a[parent], &a[minchild]);
			parent = minchild;
			minchild = 2 * parent - 1;
		}
		else
		{
			break;
		}
	}


}

// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;

	Adjustdown(hp->a, hp->a[0],hp->size);

}







// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	return hp->a[0];
	
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
	return hp->size;
}

// 堆的判空
bool HeapEmpty(Heap* hp)
{
	assert(hp);


	return hp->size == 0;
}
//mark up准备第二次写堆